package com.shm.leetcode;

/**
 * 1796. 字符串中第二大的数字
 * 给你一个混合字符串 s ，请你返回 s 中 第二大 的数字，如果不存在第二大的数字，请你返回 -1 。
 * <p>
 * 混合字符串 由小写英文字母和数字组成。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "dfa12321afd"
 * 输出：2
 * 解释：出现在 s 中的数字包括 [1, 2, 3] 。第二大的数字是 2 。
 * 示例 2：
 * <p>
 * 输入：s = "abc1111"
 * 输出：-1
 * 解释：出现在 s 中的数字只包含 [1] 。没有第二大的数字。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= s.length <= 500
 * s 只包含小写英文字母和（或）数字。
 */
public class SecondHighest {
    /**
     * @param s
     * @return
     */
    public int secondHighest(String s) {
        char max = '0';
        char second = '0';
        boolean zeroFlag = false;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= '0' && c <= '9') {
                if (c == '0') {
                    zeroFlag = true;
                }
                if (c >= max) {
                    if (c > max) {
                        second = max;
                    }
                    max = c;
                } else if (c > second) {
                    second = c;
                }
            }
        }
        if (!zeroFlag && second < max) {
            return Integer.parseInt(String.valueOf(second));
        }
        if (zeroFlag && max != '0' && second == '0') {
            return Integer.parseInt(String.valueOf(second));
        }
        return -1;
    }

    /**
     * 方法一：直接遍历
     * 思路与算法
     *
     * 题目要求找到字符串 ss 中第二大的数字，我们用 \textit{first}first、\textit{second}second 分别记录 ss 中第一大的数字与第二大的数字，且初始化时二者均为 -1−1，当我们遍历字符串中第 ii 个字符 s[i]s[i] 时：
     *
     * 如果第 s[i]s[i] 为字母则跳过；
     * 如果第 s[i]s[i] 为数字，则令 \textit{num}num 表示 s[i]s[i] 对应的十进制数字：
     * 如果满足 \textit{num} > \textit{first}num>first，则当前最大的数字为 \textit{num}num，第二大的数字为 \textit{first}first，则此时更新 \textit{second}second 等于当前的 \textit{first}first，更新当前的 \textit{first}first 为 \textit{num}num 即可。
     * 如果满足 \textit{second} < \textit{num} < \textit{first}second<num<first，则当前最大的数字为 \textit{first}first，第二大的数字为 \textit{num}num，则此时更新当前的 \textit{second}second 为 \textit{num}num 即可。
     * 如果满足 \textit{num} \le \textit{second}num≤second，则此时不需要任何更新。
     * 最终返回第二大数字 \textit{second}second 即可。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode.cn/problems/second-largest-digit-in-a-string/solution/zi-fu-chuan-zhong-di-er-da-de-shu-zi-by-ujgwp/
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 表示字符串的长度。我们只需遍历一遍字符串即可。
     *
     * 空间复杂度：O(1)O(1)。仅需常数个空间即可。
     * @param s
     * @return
     */
    public int secondHighest_1(String s) {
        int first = -1, second = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = c - '0';
                if (num > first) {
                    second = first;
                    first = num;
                } else if (second < first && num > second) {
                    second = num;
                }
            }
        }
        return second;
    }
}
